package sort

/**
 * 排序算法	平均时间复杂度
 * 选择排序     O(n2)
 * 基本思想
 * 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
 * 第二次遍历n-2个数，找到最小的数值与第二个元素交换；
 * 。。。
 * 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
 */

fun main(arr: Array<String>) {
    selectionSort(getItems())
}

/**
 * 选择排序
 */
fun selectionSort(arr: ArrayList<Int>) {

    for (i in arr.indices) {//遍历集合
        var index = i
        //遍历i..lastIndex，找到最小数
        for (j in (i + 1)..arr.lastIndex) {
            if (arr[j] < arr[index]) {
                index = j
            }
        }

        //如果最小数位置发生变化，则交换位置
        if (index != i) {
            var temp = arr[index]
            arr[index] = arr[i]
            arr[i] = temp
        }
    }

    println(arr.toList())
}
